package link

import (
	"algorithm/myStruct"
	"container/list"
	"errors"
)

// --------------------------ListStack---------------------------------
type ListStack struct {
	l *myStruct.List
}

func NewListStack() *ListStack {
	return &ListStack{l: myStruct.NewList()}
}

func (s *ListStack) Push(e interface{}) {
	s.l.PushFront(e)
}

func (s *ListStack) Pop() interface{} {
	e := s.l.PopFront()
	if e == nil {
		return nil
	}

	return e.Val
}

// --------------------------ListStack---------------------------------

// --------------------------ArrayStack---------------------------------
type ArrayStack struct {
	a        []interface{}
	popIndex int
	size     int
}

func NewArrStack(size int) *ArrayStack {
	return &ArrayStack{
		a:        make([]interface{}, size),
		size:     size,
		popIndex: -1,
	}
}

func (as *ArrayStack) Push(e interface{}) error {
	if as.popIndex+1 == as.size {
		return errors.New("stack full")
	}

	as.popIndex++
	as.a[as.popIndex] = e

	return nil
}

func (as *ArrayStack) Pop() interface{} {
	if as.popIndex < 0 {
		return nil
	}

	as.popIndex--

	return as.a[as.popIndex+1]
}

// --------------------------ArrayStack---------------------------------

// --------------------------minStack---------------------------------
// 最小栈 https://leetcode-cn.com/problems/min-stack/
type MinStack struct {
	dataStack *list.List
	minStack  *list.List
}

func Constructor() MinStack {
	return MinStack{dataStack: list.New(), minStack: list.New()}
}

func (ms *MinStack) Push(val int) {
	ms.dataStack.PushBack(val)

	minVal := ms.minStack.Back()
	if minVal == nil || minVal.Value.(int) > val {
		ms.minStack.PushBack(val)
	} else {
		ms.minStack.PushBack(minVal.Value)
	}
}

func (ms *MinStack) Pop() {
	ms.minStack.Remove(ms.minStack.Back())
	ms.dataStack.Remove(ms.dataStack.Back())
}

func (ms *MinStack) Top() int {
	e := ms.dataStack.Back()
	return e.Value.(int)
}

func (ms *MinStack) GetMin() int {
	e := ms.minStack.Back()
	return e.Value.(int)
}

// --------------------------minStack---------------------------------

// --------------------------queueStack---------------------------------
// 队列实现栈  https://leetcode-cn.com/problems/implement-stack-using-queues/
type MyStack struct {
	que1 *list.List
	que2 *list.List
}

func Constructor1() MyStack {
	return MyStack{
		que1: list.New(),
		que2: list.New(),
	}
}

func (this *MyStack) Push(x int) {
	if this.que1.Len() > 0 {
		this.que1.PushFront(x)
	} else if this.que2.Len() > 0 {
		this.que2.PushFront(x)
	} else {
		this.que1.PushFront(x)
	}
}

func (this *MyStack) Pop() int {
	if this.que1.Len() > 0 {
		for this.que1.Len() != 1 {
			this.que2.PushFront(this.que1.Remove(this.que1.Back()))
		}
		return this.que1.Remove(this.que1.Back()).(int)
	} else if this.que2.Len() > 0 {
		for this.que2.Len() != 1 {
			this.que1.PushFront(this.que2.Remove(this.que2.Back()))
		}
		return this.que2.Remove(this.que2.Back()).(int)
	}
	return 0
}

func (this *MyStack) Top() int {
	if this.que1.Len() > 0 {
		for this.que1.Len() != 1 {
			this.que2.PushFront(this.que1.Remove(this.que1.Back()))
		}
		e := this.que1.Remove(this.que1.Back()).(int)
		this.que2.PushFront(e)
		return e
	} else if this.que2.Len() > 0 {
		for this.que2.Len() != 1 {
			this.que1.PushFront(this.que2.Remove(this.que2.Back()))
		}
		e := this.que2.Remove(this.que2.Back()).(int)
		this.que1.PushFront(e)

		return e
	}
	return 0
}

func (this *MyStack) Empty() bool {
	return this.que1.Len() == 0 && this.que2.Len() == 0
}

// --------------------------queueStack---------------------------------
